package com.example.stack;

import org.apache.commons.lang3.StringUtils;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * V2.0简化代码
 *
 * 中缀表达式符合人的直觉，但是不利于计算机计算
 * 后缀表达式（逆波兰表达式）更适合计算机计算，但是不符合直接，很难写出
 * 通过算法将中缀表达式转换成后缀表达式然后计算出结果
 *
 * @Author: wanqian
 * @Date: 2021/1/29 10:31
 */
public class SuffixExpression2 {

    public static final String expression = "7+2-(8-2)*5-5*3-4+20*2-3*7+35";

    public static void main(String[] args) {
        //将中缀表达式转换成List
        List<String> infixList = parseExpression2List(expression);
        //将中缀表达式List转换成后缀表达式List
        List<String> suffixList = parseSuffixExpressionList(infixList);
        //计算结果
        int result = calculateSuffix(suffixList);
        System.out.println(String.format("%s = %d", expression, result));
    }

    /**
     * 计算后缀表达式
     *
     * @param suffixList
     * @return
     */
    public static int calculateSuffix(List<String> suffixList) {
        Stack<Integer> numStack = new Stack<>();
        for (String ele : suffixList) {
            if (ele.matches("\\d+")) {
                //将数字压入数栈
                numStack.push(Integer.valueOf(ele));
            } else {
                Integer num1 = numStack.pop();
                Integer num2 = numStack.pop();
                switch (ele) {
                    case "+":
                        numStack.push(num2 + num1);
                        break;
                    case "-":
                        numStack.push(num2 - num1);
                        break;
                    case "*":
                        numStack.push(num2 * num1);
                        break;
                    case "/":
                        numStack.push(num2 / num1);
                        break;
                    default:
                        System.out.println("运算符有误！");
                }
            }
        }
        return numStack.pop();
    }

    /**
     * 将字符串表达式转换成List
     *
     * @param expression
     * @return
     */
    public static List<String> parseExpression2List(String expression) {
        if (StringUtils.isBlank(expression)) {
            throw new RuntimeException("表达式为空!");
        }

        char[] chars = expression.toCharArray();
        ArrayList<String> suffixList = new ArrayList<>();
        StringBuilder sb = new StringBuilder(32);
        for (int i = 0; i < chars.length; i++) {
            char ch = chars[i];
            //若为数字
            if (String.valueOf(ch).matches("\\d")) {
                //考虑到多位数的情况
                sb.append(ch);
                if (i == chars.length - 1) {
                    suffixList.add(sb.toString());
                }
            } else {
                //若为符号，则先将之前的数字保存
                if (sb.length() != 0) {
                    suffixList.add(sb.toString());
                    sb.setLength(0);
                }
                //保存符号
                suffixList.add(String.valueOf(ch));
            }
        }
        return suffixList;
    }

    /**
     * 将中缀表达式转换成后缀表达式
     *
     * @param infixList
     * @return
     */
    public static List<String> parseSuffixExpressionList(List<String> infixList) {
        //tempStack只有入栈操作，直接使用ArrayList保存即可
        ArrayList<String> tempStack = new ArrayList<>();
        Stack<String> operatorStack = new Stack();

        for (String ele : infixList) {
            if (ele.matches("\\d+")) {
                //数字则直接放入临时栈
                tempStack.add(ele);
            } else if (ele.equals(")")) {
                //若为右括号，则将符号栈中的符号依次放入临时栈，直到遇到左括号
                while (!operatorStack.peek().equals("(")) {
                    tempStack.add(operatorStack.pop());
                }
                //抛出左括号
                operatorStack.pop();
            } else if (ele.equals("(")) {
                operatorStack.push(ele);
            } else {
                //若当前运算符优先级小于等于栈顶运算符，则将栈顶运算符转移至临时栈
                //左括号优先级改为最低，遇到左括号则会入栈，无需判断
                //由于左括号优先级最低，其入栈操作在之前做了单独判断
                while (!operatorStack.isEmpty()
                        && getPriority(ele) <= getPriority(operatorStack.peek())) {
                    tempStack.add(operatorStack.pop());
                }
                //当遇到左括号，栈为空或栈顶运算符优先级更小则入栈
                operatorStack.push(ele);
            }
        }
        //将操作符栈剩余操作符压入临时栈
        //实际上stack中数组保存的元素顺序即为最终结果。但由于取值都从末尾逆向取，所以出栈顺序是相反的。
        while (!operatorStack.isEmpty()) {
            tempStack.add(operatorStack.pop());
        }
        return tempStack;
    }

    /**
     * 判断符号优先级
     *
     * @param operation
     * @return
     */
    public static int getPriority(String operation) {
        //左括号优先级最低，使得其他运算符可以置于其之上
        int LEFT_BRACKET = 0;
        int ADD = 1;
        int SUB = 1;
        int MUL = 2;
        int DIV = 2;

        int result = 0;
        switch (operation) {
            case "(":
                result = LEFT_BRACKET;
                break;
            case "+":
                result = ADD;
                break;
            case "-":
                result = SUB;
                break;
            case "*":
                result = MUL;
                break;
            case "/":
                result = DIV;
                break;
            default:
                System.out.println("不存在该运算符" + operation);
                break;
        }
        return result;
    }
}
